ABSTRACT
The topological distance is to measure the structural difference between two graphs in a metric space. Graphs are ubiquitous, and topological measurements over graphs arise in diverse areas, including, e.g. COVID-19 structural analysis, DNA/RNA alignment, discovering the Isomers, checking the code plagiarism. Unfortunately, popular distance scores used in these applications, that scale over large graphs, are not metrics, and the computation usually becomes NP-hard. While, fuzzy measurement is an uncertain representation to apply for a polynomial-time solution for undirected multigraph isomorphism. But the graph isomorphism problem is to determine two finite graphs that are isomorphic, which is not known with a polynomial-time solution. This paper solves the undirected multigraph isomorphism problem with an algorithmic approach as NP=P and proposes a polynomial-time solution to check if two undirected multigraphs are isomorphic or not. Based on the solution, we define a new fuzzy measurement based on graph isomorphism for topological distance/structural similarity between two graphs. Thus, this paper proposed a fuzzy measure of the topological distance between two undirected multigraphs. If two graphs are isomorphic, the topological distance is 0;if not, we will calculate the Euclidean distance among eight extracted features and provide the fuzzy distance. The fuzzy measurement executes more efficiently and accurately than the current methods.
ABSTRACT
The topological distance is to measure the structural difference between two graphs in a metric space. Graphs are ubiquitous, and topological measurements over graphs arise in diverse areas, including, e.g. COVID-19 structural analysis, DNA/RNA alignment, discovering the Isomers, checking the code plagiarism. Unfortunately, popular distance scores used in these applications, that scale over large graphs, are not metrics, and the computation usually becomes NP-hard. While, fuzzy measurement is an uncertain representation to apply for a polynomial-time solution for undirected multigraph isomorphism. But the graph isomorphism problem is to determine two finite graphs that are isomorphic, which is not known with a polynomial-time solution. This paper solves the undirected multigraph isomorphism problem with an algorithmic approach as NP=P and proposes a polynomial-time solution to check if two undirected multigraphs are isomorphic or not. Based on the solution, we define a new fuzzy measurement based on graph isomorphism for topological distance/structural similarity between two graphs. Thus, this paper proposed a fuzzy measure of the topological distance between two undirected multigraphs. If two graphs are isomorphic, the topological distance is 0;if not, we will calculate the Euclidean distance among eight extracted features and provide the fuzzy distance. The fuzzy measurement executes more efficiently and accurately than the current methods. © 2020 IEEE.